|
Wheel factorization is a method for performing a preliminary reduction in the number of potential primes from the initial set of all natural numbers 2 and greater; possibly prior to passing the result list of potential primes to the Sieve of Eratosthenes or other sieve that separates prime numbers from composites, but may further be used as a prime number wheel sieve in its own right by recursively applying the factorization wheel generation algorithm. Much definitive work on wheel factorization, sieves using wheel factorization, and wheel sieve, was done by Paul Pritchard〔Pritchard, Paul, "Linear prime-number sieves: a family tree," ''Sci. Comput. Programming'' 9:1 (1987), pp. 17–35.〕〔Paul Pritchard, A sublinear additive sieve for finding prime numbers, Communications of the ACM 24 (1981), 18–23. MR 82c:10011〕〔Paul Pritchard, Explaining the wheel sieve, Acta Informatica 17 (1982), 477–485. MR 84g:10015〕〔Paul Pritchard, Fast compact prime number sieves (among others), Journal of Algorithms 4 (1983), 332–344. MR 85h:11080〕 in formulating a series of different algorithms. To demonstrate the use of the factorization wheel graphically, one starts by writing the natural numbers around circles as shown in the adjacent diagram. Prime numbers in the innermost circle have their multiples in similar positions as themselves in the other circles, forming spokes of primes and their multiples. Multiples of the prime numbers in the innermost circle form spokes of composite numbers in the outer circles. ==Sample graphical procedure== # Find the first few prime numbers to form the basis of the factorization wheel. They are known or perhaps determined from previous applications of smaller factorization wheels or by quickly finding them using the Sieve of Eratosthenes. # Multiply the base prime numbers together to give the result ''n'' which is the circumference of the factorization wheel. # Write the numbers 1 to ''n'' in a circle. This will be the inner-most circle representing one rotation of the wheel. # From the numbers 1 to ''n'' in the innermost circle, strike off all multiples of the base primes from step one as applied in step 2. This composite number elimination can be accomplished either by use of a sieve such as the Sieve of Eratosthenes or as the result of applications of smaller factorization wheels. # Taking ''x'' to be the number of circles written so far, continue to write ''xn'' + 1 to ''xn'' + ''n'' in concentric circles around the inner-most circle, such that ''xn'' + 1 is in the same position as (''x'' − 1)''n'' + 1. # Repeat step 5 until the largest rotation circle spans the largest number to be tested for primality. # Strike off the number 1. # Strike off the spokes of the prime numbers as found in step 1 and applied in step 2 in all outer circles without striking off the prime numbers in the inner-most circle (in circle 1). # Strike off the spokes of all multiples of prime numbers struck from the inner circle 1 in step 4 in the same way as striking off the spokes of the base primes in step 8. # The remaining numbers in the wheel are mostly prime numbers (they are collectively called "relatively" prime). Use other methods such as the Sieve of Eratosthenes or further application of larger factorization wheels to remove the remaining non-primes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「wheel factorization」の詳細全文を読む スポンサード リンク
|